#! /usr/bin/env python
# -*- coding: utf-8 -*-


ugly_list = [1, 2]      # cache
divid_multi =  [
    # (24, 25),
    # (15, 16),
    # (9, 10),
    # (8, 9),
    (25, 27),
    (5, 6),
    (4, 5),
    (3, 4),
    (2, 3),
]


class Solution:
    """
    @param n: An integer
    @return: the nth prime number as description.
    """
    def nthUglyNumber(self, n):
        # write your code here
        len_ugly = len(ugly_list)

        if len_ugly >= n:
            return self.read_nth(n)

        cur_max_ugly = ugly_list[len_ugly-1]
        while len_ugly < n:
            cur_max_ugly, old = self.get_next(cur_max_ugly), cur_max_ugly
            # cur_max_ugly = self.get_next(cur_max_ugly)
            len_ugly += 1
            ugly_list.append(cur_max_ugly)
            if cur_max_ugly - old == 1 and (old, cur_max_ugly) not in divid_multi:
                print('catch')
                divid_multi.insert(0, (old, cur_max_ugly))

        assert len_ugly == n
        return cur_max_ugly

    @staticmethod
    def read_nth(n):
        return ugly_list[n-1]

    @staticmethod
    def get_next(max_ugly):
        # print(max_ugly)
        if Solution.is_ugly(max_ugly + 1):
            return max_ugly + 1

        candidate_result = []

        for d, m in divid_multi:
            # print(d,m)
            if max_ugly % d == 0:
                candidate = max_ugly // d * m
                return candidate
                # candidate_result.append(candidate)

        # return min(candidate_result)

    @staticmethod
    def is_ugly(num):
        assert num >= 2
        nlist = [2, 3, 5]

        for divid in nlist:
            while num % divid == 0: num /= divid

        return num == 1


def main():
    from time import time
    print("start main")

    # begin = time()
    s = Solution()
    # print(s.nthUglyNumber(599))
    # print(s.nthUglyNumber(40))
    print(s.nthUglyNumber(41))
    print(ugly_list)
    print(divid_multi)
    # print(ugly_list[10])
    # print(ugly_list[11])
    # print(ugly_list[12])
    # print(s.nthUglyNumber(9))
    # print(ugly_list)
    # print(divid_multi[-10:-1:1])
    # print(s.nthUglyNumber(10))

    # pass_t = time() - begin
    # print(pass_t)
    # print(s.nthUglyNumber(11))

if __name__ == "__main__":
    main()
